package com.zhangjunkai.astar
{
	import flash.geom.Point;


	public class AStar
	{
		private var _openHeap:BinaryHeap, _touched:Vector.<AStarNodeVO>, _grid:Vector.<Vector.<AStarNodeVO>>, tcur:AStarNodeVO, currentNode:AStarNodeVO, ret:Vector.<AStarNodeVO>, neighbors:Vector.<AStarNodeVO>, neighbor:AStarNodeVO, newG:uint, i:uint, j:uint;

		public static const Direction_4:String='Direction_4'; //4方向寻路
		public static const Direction_8:String='Direction_8'; //8方向寻路

		private var thisDirection:String; //本寻路

		/**
		 * 构造方法
		 * @param grid
		 * @param directionValue 4方向寻路 或者8方向寻路
		 * @throws Error
		 */
		public function AStar(grid:Vector.<Vector.<AStarNodeVO>>, directionValue:String)
		{
			if (directionValue == Direction_4 || directionValue == Direction_8)
			{
				thisDirection=directionValue;
			}
			else
			{
				throw new Error('寻路参数不正确');
			}

			_touched=new Vector.<AStarNodeVO>(grid.length * grid.length + 1, true);
			_grid=grid;
			_openHeap=new BinaryHeap(function(node:AStarNodeVO):Number
			{
				return node.f;
			});
			if (AStar.Direction_8 == thisDirection)
			{
				fun_8();
			}
			else if (AStar.Direction_4 == thisDirection)
			{
				fun_4();
			}
		}

		private function fun_8():void
		{
			for each (var row:Vector.<AStarNodeVO> in _grid)
			{
				for each (var node:AStarNodeVO in row)
				{
					node.neighbors=new Vector.<AStarNodeVO>();
					for each (var neighbor:AStarNodeVO in getNeighbors_8(_grid, node))
					{
						if (neighbor == null)
							break;
						if (!neighbor.isWall)
							node.neighbors.push(neighbor); // in demo i focus only on query optimization
					}
				}
			}
		}

		private function fun_4():void
		{
			for each (var row:Vector.<AStarNodeVO> in _grid)
			{
				for each (var node:AStarNodeVO in row)
				{
					node.neighbors=new Vector.<AStarNodeVO>();
					for each (var neighbor:AStarNodeVO in getNeighbors_4(_grid, node))
					{
						if (neighbor == null)
							break;
						if (!neighbor.isWall)
							node.neighbors.push(neighbor); // in demo i focus only on query optimization
					}
				}
			}
		}

		/**
		 *
		 * DEBUG ONLY.
		 */
		public function get evaluatedTiles():Vector.<AStarNodeVO>
		{
			return _touched;
		}

		public function search(start:AStarNodeVO, end:AStarNodeVO):Vector.<AStarNodeVO>
		{
			i=0;
			tcur=_touched[0];
			while (tcur)
			{
				tcur.f=0;
				tcur.g=0;
				tcur.h=0;
				tcur.closed=false;
				tcur.visited=false;
				tcur.parent=null;
				tcur.next=null;
				_touched[i]=null;

				i++;
				tcur=_touched[i];
			}
			_openHeap.reset();
			i=0; // touched count -- lol, imperative programming (optimizer :()


			_openHeap.push(start);

			while (_openHeap.size > 0)
			{
				currentNode=_openHeap.pop();

				if (currentNode == end)
				{
					i=0;
					while (currentNode.parent)
					{
						currentNode.parent.next=currentNode;
						i++;
						currentNode=currentNode.parent;
					}
					ret=new Vector.<AStarNodeVO>(i + 1, true);
					for (j=0; currentNode; j++)
					{
						ret[j]=currentNode;
						currentNode=currentNode.next;
					}
					return ret;
				}

				currentNode.closed=true;
				_touched[i++]=currentNode;

				for each (neighbor in currentNode.neighbors)
				{
					if (neighbor.closed)
						continue;

					newG=currentNode.g + currentNode.cost;

					if (!neighbor.visited)
					{

						_touched[i++]=neighbor;

						neighbor.visited=true;
						neighbor.parent=currentNode;
						neighbor.g=newG;
						neighbor.h=heuristic(neighbor.position, end.position);
						neighbor.f=newG + neighbor.h;
						_openHeap.push(neighbor);

					}
					else if (newG < neighbor.g)
					{

						neighbor.parent=currentNode;
						neighbor.g=newG;
						neighbor.f=newG + neighbor.h;

						_openHeap.rescoreElement(neighbor);
					}

				}
			}

			return ret;
		}


		private function getNeighbors_8(grid:Vector.<Vector.<AStarNodeVO>>, node:AStarNodeVO):Vector.<AStarNodeVO>
		{
			var ret:Vector.<AStarNodeVO>=new Vector.<AStarNodeVO>(8, true), x:uint=node.position.x, y:uint=node.position.y, gridWidth:uint=grid.length, gridHeight:uint=grid[x].length, id:uint;

			if (x > 0)
			{
				ret[id++]=grid[x - 1][y];
				if (y > 0 && AStar.Direction_8 == thisDirection)
				{
					ret[id++]=grid[x - 1][y - 1];
				}
				if (y < gridHeight - 1 && AStar.Direction_8 == thisDirection)
				{
					ret[id++]=grid[x - 1][y + 1];
				}
			}
			if (x < gridWidth - 1)
			{
				ret[id++]=grid[x + 1][y];
				if (y > 0 && AStar.Direction_8 == thisDirection)
				{
					ret[id++]=grid[x + 1][y - 1];
				}
				if (y < gridHeight - 1 && AStar.Direction_8 == thisDirection)
				{
					ret[id++]=grid[x + 1][y + 1];
				}
			}
			if (y > 0)
			{
				ret[id++]=grid[x][y - 1];
			}
			if (y < gridHeight - 1)
			{
				ret[id++]=grid[x][y + 1];
			}
			return ret;
		}

		private function getNeighbors_4(grid:Vector.<Vector.<AStarNodeVO>>, node:AStarNodeVO):Vector.<AStarNodeVO>
		{
			var ret:Vector.<AStarNodeVO>=new Vector.<AStarNodeVO>(8, true), x:uint=node.position.x, y:uint=node.position.y, gridWidth:uint=grid.length, gridHeight:uint=grid[x].length, id:uint;

			if (x > 0)
			{
				ret[id++]=grid[x - 1][y];
			}
			if (x < gridWidth - 1)
			{
				ret[id++]=grid[x + 1][y];
			}
			if (y > 0)
			{
				ret[id++]=grid[x][y - 1];
			}
			if (y < gridHeight - 1)
			{
				ret[id++]=grid[x][y + 1];
			}
			return ret;
		}

		private function heuristic(pos0:Point, pos1:Point):uint
		{
			var d1:int=pos1.x - pos0.x, d2:int=pos1.y - pos0.y;
			d1=d1 < 0 ? -d1 : d1;
			d2=d2 < 0 ? -d2 : d2;
			//diag = d1 < d2 ? d1 : d2;
			//return  Math.SQRT2 * diag + d1 + d2 - 2 * diag;
			return d1 + d2;
		}

	}
}


